题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3325
离线版题目:http://paste.ubuntu.com/18029355/
数据生成器:http://paste.ubuntu.com/18029394/
最近都在做字符串,所以接触了一点逆向字符串的题目,于是这题就会做啦!
这类给你字符串结构的过程数组,叫你统计方案数/构造符合要求的字符串,说到底就是给了你一堆字符等与不等的关系
而你就需要根据具体数据结构的特点来处理这些关系
比如说这道题,我上周六想了半个小时,一点思路都没有,觉得提供的关系可能是O(n^2)的。
但今天再来想的时候发现,相等关系可以用和manacher时间复杂度一样的整法证到时O(n)的
而不等关系很明显是O(n)的,于是保存好关系,并查集缩一缩点就搞好啦!
基本上1A! 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
#include<iostream> #include<cstdio> #include<set> #define SITR set<int>::iterator using namespace std; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return buf*f; } const int MAXN = 100000+9; const int SIGMA_SIZE = 26; int ld[MAXN],lo[MAXN],fa[MAXN]; int n,mx=1,vout[MAXN],col[MAXN]; set<int> Q[MAXN]; inline int find(int w){ int f=fa[w],tmp; while (fa[f] != f) f=fa[f]; while (w != f) tmp=fa[w],fa[w]=f,w=tmp; return f; } inline void connect(int a, int b){ int f1=find(a), f2=find(b); if (f1 != f2) fa[f1] = f2; } inline void discon(int a, int b){ Q[fa[a]].insert(fa[b]); Q[fa[b]].insert(fa[a]); } int main(){ n = read(); for (int i=1;i<=n;i++) fa[i] = i; for (int i=1;i<=n;i++) ld[i] = (read()-1)/2; for (int i=1;i<n;i++) lo[i] = read()/2; for (int i=1;i<=n;i++){ for (int j=max(mx-i+1,1);j<=ld[i];j++) connect(i+j,i-j); mx = max(mx, i+ld[i]); for (int j=max(mx-i+1,1);j<=lo[i];j++) connect(i+j,i-j+1); mx = max(mx, i+lo[i]); } for (int i=1;i<=n;i++) fa[i]=find(i); for (int i=1;i<=n;i++){ if (i-ld[i] > 1 && i+ld[i] < n) discon(i+ld[i]+1,i-ld[i]-1); if (i-lo[i] > 0 && i+lo[i] < n) discon(i+lo[i]+1,i-lo[i]); } for (int i=1;i<=n;i++){ if (vout[fa[i]]) continue; else { for (SITR j=Q[fa[i]].begin();j!=Q[fa[i]].end();j++) col[vout[*j]] = i; for (int j=1;j<=SIGMA_SIZE;j++) if (col[j] < i) {vout[fa[i]] = j; break;} } } for (int i=1;i<=n;i++) putchar(vout[fa[i]]+'a'-1); return 0; }
哇塞,居然是沙发?留个名
Great write-up, I?¦m regular visitor of one?¦s blog, maintain up the excellent operate, and It is going to be a regular visitor for a long time.
I will immediately grab your rss as I can not find your email subscription link or e-newsletter service. Do you have any? Please let me know in order that I could subscribe. Thanks.